package LeetCode.interview;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;

import LeetCode.interview._101_Symmetric_Tree.TreeNode;

import util.LogUtils;

/*
 * 
原题

　Given numRows, generate the first numRows of Pascal's triangle.

	For example, given numRows = 5,
	Return

	   [
            [1],
    	   [1,1],
   		  [1,2,1],
  		 [1,3,3,1],
 		[1,4,6,4,1]
	   ]

题目大意

	Pascal's_Triangle：就是杨辉三角
解题思路
	这道题比较简单，属于基础的数组操作。
	基本思路是每层保存前一行的指针，然后当前航数据根据上一行来得到，每个元素就是上一行两个相邻元素相加（第一个和最后一个元素是1）。
	算法时间复杂度应该是O(1+2+3+...+n)=O(n^2)，空间上只需要二维数组来存储结果，不需要额外空间。代码如下： 
 * @Date 2017-09-14 09：44
 */
public class _118_Pascals_Triangle {
	
	public class TreeNode {
	    int val;
	    TreeNode left;
	    TreeNode right;
	    TreeNode(int x) { val = x; }
	    public TreeNode(int x, TreeNode l, TreeNode r) {val = x; left = l; right = r;}
	}
	
	/**
	 * 生成杨辉三角
	 * @param numRows
	 * @return
	 */
	public List<List<Integer>> generate(int numRows) {  
		List<List<Integer>> rs = new ArrayList<>();
		if (numRows == 0)	return rs;
		List<Integer> pre =  new ArrayList<>();		//前一行
		pre.add(1);											//第一行
		rs.add(pre);
		//从第二行开始遍历
		for (int i = 2; i <= numRows; i ++) {
			List<Integer> curRows =  new ArrayList<>();
			curRows.add(1);
			for (int j = 0; j < pre.size()-1; j ++) {
				curRows.add(pre.get(j)+pre.get(j+1));
			}
			curRows.add(1);	
			rs.add(curRows);
			pre = curRows;
		}
//		traverse(rs);
		return rs;
	}
	
	private TreeNode newTree2() {
		return new TreeNode(1, 
					new TreeNode(2, 
							new TreeNode(4, 
									new TreeNode(6), new TreeNode(7,
															null, new TreeNode(8))
							), new TreeNode(5)
					), 
					new TreeNode(3, 
							null, 	null)
				);
	}
	
	
	private TreeNode newTree1() {
		return new TreeNode(1, 
					null, null
				);
	}
	
	
	//中序遍历：看下结果
    public void traverse (ArrayList<ArrayList<Integer>> rs) {
    	for (ArrayList<Integer> row : rs) {
    		for (int i : row) {
    			LogUtils.print(i);
    		}
    		LogUtils.br();
    	}
    }
	
	
	public static void main(String[] args) {
		_118_Pascals_Triangle obj = new _118_Pascals_Triangle();
		LogUtils.println("结果", 
				obj.generate(
						5
				));
	}
}
